package leetcode1;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 09 - 08
 * Time:9:12
 */
public class Test02 {
    /***
     * 2.主要元素：数组中占比超过一半的元素称之为主要元素；
     * 给定一个整数数组，找到它的主要元素，若没有，则返回-1；
     * [1,2,5,9,5,9,5,5,5]
     * 返回：5
     * 不是寻找出现次数最多的数字，而是查找出现次数超过长度一半的数字
     * @param nums
     * @return
     * 将数组先进行排序，当i ,j的区间长度 > len / 2，即找到了
     */
    public static int majorityElemment(int[] nums){
        //将数组先排序
        //1,2,5,5,5,5,5,9,9
        Arrays.sort(nums);
        //保证i、j区间长度大于len /2;所以j = len / 2
        //当i ,j 下标对应的数值不相等的时候；i++;j++
       int len = nums.length;
        for (int i = 0; i < len / 2; i++) {
            for (int j = i + (len / 2); j < nums.length; j++) {
                if(nums[i] == nums[j]){
                    return nums[i];
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,5,9,5,9,5,5,5};
        int ret = majorityElemment(nums);
        System.out.println(ret);
    }

}
